#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"
#include <vector>
#include <math.h>

using namespace std;

bool contain(vector<int> A,int i){
	vector<int>::iterator it;
	for(it=A.begin();it!=A.end();it++){
		if (*it==i){
			return true;
		}
	}
	return false;
}


bool coutingSort(ElemType array[],size_t arrLen) {
    if (arrLen < 2) {
        return true;
    }
    int max = array[0];
    int min = array[0];
    for (size_t i = 1; i < arrLen; ++i)
    {
        if (min > array[i]) {
            min = array[i];
        }
        else if (max < array[i]) {
            max = array[i];
        }
    }
    // Create counting buckets
    int *countingBuckets = new int[max - min + 1]();
    // Count number of values in array
    for (size_t j = 0; j < arrLen; ++j)
    {
        ++countingBuckets[array[j] - min];
    }
    // Accumulate coutingBuckets to find the last ordered location of value in array
    for (size_t k = 1; k < (max - min + 1); ++k)
    {
        countingBuckets[k] += countingBuckets[k-1];
    }
    //Traverse the array in reversed order
    int *tempArray = new int[arrLen]();
    for (int l = arrLen - 1; l >= 0; --l)
    {
        tempArray[--countingBuckets[array[l] - min]] = array[l];
    }
    for (size_t m = 0; m < arrLen; ++m)
    {
        array[m] = tempArray[m];
    }
    delete [] countingBuckets;
    delete [] tempArray;
    return true;
}

void printArray(int array[],size_t arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}



int main()
{
	LinkList *L1,*L2;
	ElemType A[10]={1,2,3,4,5,6,7,8,9,10};
	
	InitList(L1);
	CreateListR(L1,A,10);
	printf("输入A中的数据元素: \n");
	DispList(L1);
	
	
	ElemType B[8]={2,0,0,5,2,0,6,2};
	size_t arrLen = sizeof(B)/sizeof(B[0]);
	printf("排序前，输入B中的数据元素：\n");
	printArray(B,arrLen);
	coutingSort(B,arrLen);
	
	InitList(L2);
	CreateListR(L2,B,8);
	printf("排序后，输入B中的数据元素：\n");
	DispList(L2);
	vector<int> vect;
	for (int i = 0 ;i < 8 ; i++){
		if (!contain(vect,B[i])){
			vect.push_back(B[i]);
		}
	}
	
	
	vector<int>::iterator it;
	printf("转纯集合，所以B中的数据元素为：\n");
	ElemType C[vect.size()];
	int i = 0;
	for(it=vect.begin();it!=vect.end();it++){
		int j = *it;
		C[i] = j;
		i++;
	}
	InitList(L2);
	CreateListR(L2,C,vect.size());
	DispList(L2);
	
	printf("\n");
	
	LNode *p2 = L2->next;
	
	while(p2!=NULL){
		
		if (LocateElem(L1,p2->data)==0){
			ListInsert(L1,1,p2->data);
		}
		p2 = p2->next;
	}
	
	
	
	
	
	
	
	printf("求并集：A=A∪B: \n");
	DispList(L1);
	printf("\n");
	return 0;
	
}


